package com.ctrip.study.algorithm.leetcode;

import org.junit.Test;

import junit.framework.TestCase;

/**
 * Given a sorted array and a target value, return the index if the target is
 * found. If not, return the index where it would be if it were inserted in
 * order. You may assume no duplicates in the array. Here are few examples.
 * [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0.
 */
public class SearchInsertPosition extends TestCase {

	public int searchInsert(int[] A, int target) {
		int low = 0;
		int high = A.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (A[mid] > target)
				high = mid - 1;
			else if (A[mid] < target)
				low = mid + 1;
			else
				return mid;
		}
		return low;
	}

	@Test
	public void test() {
		SearchInsertPosition sp = new SearchInsertPosition();
		int[] array = { 1, 3, 5, 6 };
		assertEquals(2, sp.searchInsert(array, 5));
		assertEquals(1, sp.searchInsert(array, 2));
		assertEquals(4, sp.searchInsert(array, 7));
		assertEquals(0, sp.searchInsert(array, 0));
	}

}
